Autogenerated HTML docs for v1.9.0-138-g2de34
diff --git a/technical/api-hash.txt b/technical/api-hash.txt deleted file mode 100644 index e5061e0..0000000 --- a/technical/api-hash.txt +++ /dev/null
@@ -1,52 +0,0 @@ -hash API -======== - -The hash API is a collection of simple hash table functions. Users are expected -to implement their own hashing. - -Data Structures ---------------- - -`struct hash_table`:: - - The hash table structure. The `array` member points to the hash table - entries. The `size` member counts the total number of valid and invalid - entries in the table. The `nr` member keeps track of the number of - valid entries. - -`struct hash_table_entry`:: - - An opaque structure representing an entry in the hash table. The `hash` - member is the entry's hash key and the `ptr` member is the entry's - value. - -Functions ---------- - -`init_hash`:: - - Initialize the hash table. - -`free_hash`:: - - Release memory associated with the hash table. - -`insert_hash`:: - - Insert a pointer into the hash table. If an entry with that hash - already exists, a pointer to the existing entry's value is returned. - Otherwise NULL is returned. This allows callers to implement - chaining, etc. - -`lookup_hash`:: - - Lookup an entry in the hash table. If an entry with that hash exists - the entry's value is returned. Otherwise NULL is returned. - -`for_each_hash`:: - - Call a function for each entry in the hash table. The function is - expected to take the entry's value as its only argument and return an - int. If the function returns a negative int the loop is aborted - immediately. Otherwise, the return value is accumulated and the sum - returned upon completion of the loop.
diff --git a/technical/api-hashmap.html b/technical/api-hashmap.html new file mode 100644 index 0000000..44c4d36 --- /dev/null +++ b/technical/api-hashmap.html
@@ -0,0 +1,985 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" + "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> +<head> +<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" /> +<meta name="generator" content="AsciiDoc 8.6.6" /> +<title>hashmap API</title> +<style type="text/css"> +/* Shared CSS for AsciiDoc xhtml11 and html5 backends */ + +/* Default font. */ +body { + font-family: Georgia,serif; +} + +/* Title font. */ +h1, h2, h3, h4, h5, h6, +div.title, caption.title, +thead, p.table.header, +#toctitle, +#author, #revnumber, #revdate, #revremark, +#footer { + font-family: Arial,Helvetica,sans-serif; +} + +body { + margin: 1em 5% 1em 5%; +} + +a { + color: blue; + text-decoration: underline; +} +a:visited { + color: fuchsia; +} + +em { + font-style: italic; + color: navy; +} + +strong { + font-weight: bold; + color: #083194; +} + +h1, h2, h3, h4, h5, h6 { + color: #527bbd; + margin-top: 1.2em; + margin-bottom: 0.5em; + line-height: 1.3; +} + +h1, h2, h3 { + border-bottom: 2px solid silver; +} +h2 { + padding-top: 0.5em; +} +h3 { + float: left; +} +h3 + * { + clear: left; +} +h5 { + font-size: 1.0em; +} + +div.sectionbody { + margin-left: 0; +} + +hr { + border: 1px solid silver; +} + +p { + margin-top: 0.5em; + margin-bottom: 0.5em; +} + +ul, ol, li > p { + margin-top: 0; +} +ul > li { color: #aaa; } +ul > li > * { color: black; } + +pre { + padding: 0; + margin: 0; +} + +#author { + color: #527bbd; + font-weight: bold; + font-size: 1.1em; +} +#email { +} +#revnumber, #revdate, #revremark { +} + +#footer { + font-size: small; + border-top: 2px solid silver; + padding-top: 0.5em; + margin-top: 4.0em; +} +#footer-text { + float: left; + padding-bottom: 0.5em; +} +#footer-badges { + float: right; + padding-bottom: 0.5em; +} + +#preamble { + margin-top: 1.5em; + margin-bottom: 1.5em; +} +div.imageblock, div.exampleblock, div.verseblock, +div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock, +div.admonitionblock { + margin-top: 1.0em; + margin-bottom: 1.5em; +} +div.admonitionblock { + margin-top: 2.0em; + margin-bottom: 2.0em; + margin-right: 10%; + color: #606060; +} + +div.content { /* Block element content. */ + padding: 0; +} + +/* Block element titles. */ +div.title, caption.title { + color: #527bbd; + font-weight: bold; + text-align: left; + margin-top: 1.0em; + margin-bottom: 0.5em; +} +div.title + * { + margin-top: 0; +} + +td div.title:first-child { + margin-top: 0.0em; +} +div.content div.title:first-child { + margin-top: 0.0em; +} +div.content + div.title { + margin-top: 0.0em; +} + +div.sidebarblock > div.content { + background: #ffffee; + border: 1px solid #dddddd; + border-left: 4px solid #f0f0f0; + padding: 0.5em; +} + +div.listingblock > div.content { + border: 1px solid #dddddd; + border-left: 5px solid #f0f0f0; + background: #f8f8f8; + padding: 0.5em; +} + +div.quoteblock, div.verseblock { + padding-left: 1.0em; + margin-left: 1.0em; + margin-right: 10%; + border-left: 5px solid #f0f0f0; + color: #888; +} + +div.quoteblock > div.attribution { + padding-top: 0.5em; + text-align: right; +} + +div.verseblock > pre.content { + font-family: inherit; + font-size: inherit; +} +div.verseblock > div.attribution { + padding-top: 0.75em; + text-align: left; +} +/* DEPRECATED: Pre version 8.2.7 verse style literal block. */ +div.verseblock + div.attribution { + text-align: left; +} + +div.admonitionblock .icon { + vertical-align: top; + font-size: 1.1em; + font-weight: bold; + text-decoration: underline; + color: #527bbd; + padding-right: 0.5em; +} +div.admonitionblock td.content { + padding-left: 0.5em; + border-left: 3px solid #dddddd; +} + +div.exampleblock > div.content { + border-left: 3px solid #dddddd; + padding-left: 0.5em; +} + +div.imageblock div.content { padding-left: 0; } +span.image img { border-style: none; } +a.image:visited { color: white; } + +dl { + margin-top: 0.8em; + margin-bottom: 0.8em; +} +dt { + margin-top: 0.5em; + margin-bottom: 0; + font-style: normal; + color: navy; +} +dd > *:first-child { + margin-top: 0.1em; +} + +ul, ol { + list-style-position: outside; +} +ol.arabic { + list-style-type: decimal; +} +ol.loweralpha { + list-style-type: lower-alpha; +} +ol.upperalpha { + list-style-type: upper-alpha; +} +ol.lowerroman { + list-style-type: lower-roman; +} +ol.upperroman { + list-style-type: upper-roman; +} + +div.compact ul, div.compact ol, +div.compact p, div.compact p, +div.compact div, div.compact div { + margin-top: 0.1em; + margin-bottom: 0.1em; +} + +tfoot { + font-weight: bold; +} +td > div.verse { + white-space: pre; +} + +div.hdlist { + margin-top: 0.8em; + margin-bottom: 0.8em; +} +div.hdlist tr { + padding-bottom: 15px; +} +dt.hdlist1.strong, td.hdlist1.strong { + font-weight: bold; +} +td.hdlist1 { + vertical-align: top; + font-style: normal; + padding-right: 0.8em; + color: navy; +} +td.hdlist2 { + vertical-align: top; +} +div.hdlist.compact tr { + margin: 0; + padding-bottom: 0; +} + +.comment { + background: yellow; +} + +.footnote, .footnoteref { + font-size: 0.8em; +} + +span.footnote, span.footnoteref { + vertical-align: super; +} + +#footnotes { + margin: 20px 0 20px 0; + padding: 7px 0 0 0; +} + +#footnotes div.footnote { + margin: 0 0 5px 0; +} + +#footnotes hr { + border: none; + border-top: 1px solid silver; + height: 1px; + text-align: left; + margin-left: 0; + width: 20%; + min-width: 100px; +} + +div.colist td { + padding-right: 0.5em; + padding-bottom: 0.3em; + vertical-align: top; +} +div.colist td img { + margin-top: 0.3em; +} + +@media print { + #footer-badges { display: none; } +} + +#toc { + margin-bottom: 2.5em; +} + +#toctitle { + color: #527bbd; + font-size: 1.1em; + font-weight: bold; + margin-top: 1.0em; + margin-bottom: 0.1em; +} + +div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 { + margin-top: 0; + margin-bottom: 0; +} +div.toclevel2 { + margin-left: 2em; + font-size: 0.9em; +} +div.toclevel3 { + margin-left: 4em; + font-size: 0.9em; +} +div.toclevel4 { + margin-left: 6em; + font-size: 0.9em; +} + +span.aqua { color: aqua; } +span.black { color: black; } +span.blue { color: blue; } +span.fuchsia { color: fuchsia; } +span.gray { color: gray; } +span.green { color: green; } +span.lime { color: lime; } +span.maroon { color: maroon; } +span.navy { color: navy; } +span.olive { color: olive; } +span.purple { color: purple; } +span.red { color: red; } +span.silver { color: silver; } +span.teal { color: teal; } +span.white { color: white; } +span.yellow { color: yellow; } + +span.aqua-background { background: aqua; } +span.black-background { background: black; } +span.blue-background { background: blue; } +span.fuchsia-background { background: fuchsia; } +span.gray-background { background: gray; } +span.green-background { background: green; } +span.lime-background { background: lime; } +span.maroon-background { background: maroon; } +span.navy-background { background: navy; } +span.olive-background { background: olive; } +span.purple-background { background: purple; } +span.red-background { background: red; } +span.silver-background { background: silver; } +span.teal-background { background: teal; } +span.white-background { background: white; } +span.yellow-background { background: yellow; } + +span.big { font-size: 2em; } +span.small { font-size: 0.6em; } + +span.underline { text-decoration: underline; } +span.overline { text-decoration: overline; } +span.line-through { text-decoration: line-through; } + + +/* + * xhtml11 specific + * + * */ + +tt { + font-family: monospace; + font-size: inherit; + color: navy; +} + +div.tableblock { + margin-top: 1.0em; + margin-bottom: 1.5em; +} +div.tableblock > table { + border: 3px solid #527bbd; +} +thead, p.table.header { + font-weight: bold; + color: #527bbd; +} +p.table { + margin-top: 0; +} +/* Because the table frame attribute is overriden by CSS in most browsers. */ +div.tableblock > table[frame="void"] { + border-style: none; +} +div.tableblock > table[frame="hsides"] { + border-left-style: none; + border-right-style: none; +} +div.tableblock > table[frame="vsides"] { + border-top-style: none; + border-bottom-style: none; +} + + +/* + * html5 specific + * + * */ + +.monospaced { + font-family: monospace; + font-size: inherit; + color: navy; +} + +table.tableblock { + margin-top: 1.0em; + margin-bottom: 1.5em; +} +thead, p.tableblock.header { + font-weight: bold; + color: #527bbd; +} +p.tableblock { + margin-top: 0; +} +table.tableblock { + border-width: 3px; + border-spacing: 0px; + border-style: solid; + border-color: #527bbd; + border-collapse: collapse; +} +th.tableblock, td.tableblock { + border-width: 1px; + padding: 4px; + border-style: solid; + border-color: #527bbd; +} + +table.tableblock.frame-topbot { + border-left-style: hidden; + border-right-style: hidden; +} +table.tableblock.frame-sides { + border-top-style: hidden; + border-bottom-style: hidden; +} +table.tableblock.frame-none { + border-style: hidden; +} + +th.tableblock.halign-left, td.tableblock.halign-left { + text-align: left; +} +th.tableblock.halign-center, td.tableblock.halign-center { + text-align: center; +} +th.tableblock.halign-right, td.tableblock.halign-right { + text-align: right; +} + +th.tableblock.valign-top, td.tableblock.valign-top { + vertical-align: top; +} +th.tableblock.valign-middle, td.tableblock.valign-middle { + vertical-align: middle; +} +th.tableblock.valign-bottom, td.tableblock.valign-bottom { + vertical-align: bottom; +} + + +/* + * manpage specific + * + * */ + +body.manpage h1 { + padding-top: 0.5em; + padding-bottom: 0.5em; + border-top: 2px solid silver; + border-bottom: 2px solid silver; +} +body.manpage h2 { + border-style: none; +} +body.manpage div.sectionbody { + margin-left: 3em; +} + +@media print { + body.manpage div#toc { display: none; } +} +</style> +<script type="text/javascript"> +/*<+'])'); + // Function that scans the DOM tree for header elements (the DOM2 + // nodeIterator API would be a better technique but not supported by all + // browsers). + var iterate = function (el) { + for (var i = el.firstChild; i != null; i = i.nextSibling) { + if (i.nodeType == 1 /* Node.ELEMENT_NODE */) { + var mo = re.exec(i.tagName); + if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") { + result[result.length] = new TocEntry(i, getText(i), mo[1]-1); + } + iterate(i); + } + } + } + iterate(el); + return result; + } + + var toc = document.getElementById("toc"); + if (!toc) { + return; + } + + // Delete existing TOC entries in case we're reloading the TOC. + var tocEntriesToRemove = []; + var i; + for (i = 0; i < toc.childNodes.length; i++) { + var entry = toc.childNodes[i]; + if (entry.nodeName == 'div' + && entry.getAttribute("class") + && entry.getAttribute("class").match(/^toclevel/)) + tocEntriesToRemove.push(entry); + } + for (i = 0; i < tocEntriesToRemove.length; i++) { + toc.removeChild(tocEntriesToRemove[i]); + } + + // Rebuild TOC entries. + var entries = tocEntries(document.getElementById("content"), toclevels); + for (var i = 0; i < entries.length; ++i) { + var entry = entries[i]; + if (entry.element.id == "") + entry.element.id = "_toc_" + i; + var a = document.createElement("a"); + a.href = "#" + entry.element.id; + a.appendChild(document.createTextNode(entry.text)); + var div = document.createElement("div"); + div.appendChild(a); + div.className = "toclevel" + entry.toclevel; + toc.appendChild(div); + } + if (entries.length == 0) + toc.parentNode.removeChild(toc); +}, + + +///////////////////////////////////////////////////////////////////// +// Footnotes generator +///////////////////////////////////////////////////////////////////// + +/* Based on footnote generation code from: + * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html + */ + +footnotes: function () { + // Delete existing footnote entries in case we're reloading the footnodes. + var i; + var noteholder = document.getElementById("footnotes"); + if (!noteholder) { + return; + } + var entriesToRemove = []; + for (i = 0; i < noteholder.childNodes.length; i++) { + var entry = noteholder.childNodes[i]; + if (entry.nodeName == 'div' && entry.getAttribute("class") == "footnote") + entriesToRemove.push(entry); + } + for (i = 0; i < entriesToRemove.length; i++) { + noteholder.removeChild(entriesToRemove[i]); + } + + // Rebuild footnote entries. + var cont = document.getElementById("content"); + var spans = cont.getElementsByTagName("span"); + var refs = {}; + var n = 0; + for (i=0; i<spans.length; i++) { + if (spans[i].className == "footnote") { + n++; + var note = spans[i].getAttribute("data-note"); + if (!note) { + // Use [\s\S] in place of . so multi-line matches work. + // Because JavaScript has no s (dotall) regex flag. + note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1]; + spans[i].innerHTML = + "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n + + "' title='View footnote' class='footnote'>" + n + "</a>]"; + spans[i].setAttribute("data-note", note); + } + noteholder.innerHTML += + "<div class='footnote' id='_footnote_" + n + "'>" + + "<a href='#_footnoteref_" + n + "' title='Return to text'>" + + n + "</a>. " + note + "</div>"; + var id =spans[i].getAttribute("id"); + if (id != null) refs["#"+id] = n; + } + } + if (n == 0) + noteholder.parentNode.removeChild(noteholder); + else { + // Process footnoterefs. + for (i=0; i<spans.length; i++) { + if (spans[i].className == "footnoteref") { + var href = spans[i].getElementsByTagName("a")[0].getAttribute("href"); + href = href.match(/#.*/)[0]; // Because IE return full URL. + n = refs[href]; + spans[i].innerHTML = + "[<a href='#_footnote_" + n + + "' title='View footnote' class='footnote'>" + n + "</a>]"; + } + } + } +}, + +install: function(toclevels) { + var timerId; + + function reinstall() { + asciidoc.footnotes(); + if (toclevels) { + asciidoc.toc(toclevels); + } + } + + function reinstallAndRemoveTimer() { + clearInterval(timerId); + reinstall(); + } + + timerId = setInterval(reinstall, 500); + if (document.addEventListener) + document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false); + else + window.onload = reinstallAndRemoveTimer; +} + +} +asciidoc.install(); +/*]]>*/ +</script> +</head> +<body class="article"> +<div id="header"> +<h1>hashmap API</h1> +</div> +<div id="content"> +<div id="preamble"> +<div class="sectionbody"> +<div class="paragraph"><p>The hashmap API is a generic implementation of hash-based key-value mappings.</p></div> +</div> +</div> +<div class="sect1"> +<h2 id="_data_structures">Data Structures</h2> +<div class="sectionbody"> +<div class="dlist"><dl> +<dt class="hdlist1"> +<tt>struct hashmap</tt> +</dt> +<dd> +<p> + The hash table structure. +</p> +<div class="paragraph"><p>The <tt>size</tt> member keeps track of the total number of entries. The <tt>cmpfn</tt> +member is a function used to compare two entries for equality. The <tt>table</tt> and +<tt>tablesize</tt> members store the hash table and its size, respectively.</p></div> +</dd> +<dt class="hdlist1"> +<tt>struct hashmap_entry</tt> +</dt> +<dd> +<p> + An opaque structure representing an entry in the hash table, which must + be used as first member of user data structures. Ideally it should be + followed by an int-sized member to prevent unused memory on 64-bit + systems due to alignment. +</p> +<div class="paragraph"><p>The <tt>hash</tt> member is the entry’s hash code and the <tt>next</tt> member points to the +next entry in case of collisions (i.e. if multiple entries map to the same +bucket).</p></div> +</dd> +<dt class="hdlist1"> +<tt>struct hashmap_iter</tt> +</dt> +<dd> +<p> + An iterator structure, to be used with hashmap_iter_* functions. +</p> +</dd> +</dl></div> +</div> +</div> +<div class="sect1"> +<h2 id="_types">Types</h2> +<div class="sectionbody"> +<div class="dlist"><dl> +<dt class="hdlist1"> +<tt>int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)</tt> +</dt> +<dd> +<p> + User-supplied function to test two hashmap entries for equality. Shall + return 0 if the entries are equal. +</p> +<div class="paragraph"><p>This function is always called with non-NULL <tt>entry</tt> / <tt>entry_or_key</tt> +parameters that have the same hash code. When looking up an entry, the <tt>key</tt> +and <tt>keydata</tt> parameters to hashmap_get and hashmap_remove are always passed +as second and third argument, respectively. Otherwise, <tt>keydata</tt> is NULL.</p></div> +</dd> +</dl></div> +</div> +</div> +<div class="sect1"> +<h2 id="_functions">Functions</h2> +<div class="sectionbody"> +<div class="dlist"><dl> +<dt class="hdlist1"> +<tt>unsigned int strhash(const char *buf)</tt> +</dt> +<dt class="hdlist1"> +<tt>unsigned int strihash(const char *buf)</tt> +</dt> +<dt class="hdlist1"> +<tt>unsigned int memhash(const void *buf, size_t len)</tt> +</dt> +<dt class="hdlist1"> +<tt>unsigned int memihash(const void *buf, size_t len)</tt> +</dt> +<dd> +<p> + Ready-to-use hash functions for strings, using the FNV-1 algorithm (see + <a href="http://www.isthe.com/chongo/tech/comp/fnv">http://www.isthe.com/chongo/tech/comp/fnv</a>). +</p> +<div class="paragraph"><p><tt>strhash</tt> and <tt>strihash</tt> take 0-terminated strings, while <tt>memhash</tt> and +<tt>memihash</tt> operate on arbitrary-length memory.</p></div> +<div class="paragraph"><p><tt>strihash</tt> and <tt>memihash</tt> are case insensitive versions.</p></div> +</dd> +<dt class="hdlist1"> +<tt>void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)</tt> +</dt> +<dd> +<p> + Initializes a hashmap structure. +</p> +<div class="paragraph"><p><tt>map</tt> is the hashmap to initialize.</p></div> +<div class="paragraph"><p>The <tt>equals_function</tt> can be specified to compare two entries for equality. +If NULL, entries are considered equal if their hash codes are equal.</p></div> +<div class="paragraph"><p>If the total number of entries is known in advance, the <tt>initial_size</tt> +parameter may be used to preallocate a sufficiently large table and thus +prevent expensive resizing. If 0, the table is dynamically resized.</p></div> +</dd> +<dt class="hdlist1"> +<tt>void hashmap_free(struct hashmap *map, int free_entries)</tt> +</dt> +<dd> +<p> + Frees a hashmap structure and allocated memory. +</p> +<div class="paragraph"><p><tt>map</tt> is the hashmap to free.</p></div> +<div class="paragraph"><p>If <tt>free_entries</tt> is true, each hashmap_entry in the map is freed as well +(using stdlib’s free()).</p></div> +</dd> +<dt class="hdlist1"> +<tt>void hashmap_entry_init(void *entry, unsigned int hash)</tt> +</dt> +<dd> +<p> + Initializes a hashmap_entry structure. +</p> +<div class="paragraph"><p><tt>entry</tt> points to the entry to initialize.</p></div> +<div class="paragraph"><p><tt>hash</tt> is the hash code of the entry.</p></div> +</dd> +<dt class="hdlist1"> +<tt>void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)</tt> +</dt> +<dd> +<p> + Returns the hashmap entry for the specified key, or NULL if not found. +</p> +<div class="paragraph"><p><tt>map</tt> is the hashmap structure.</p></div> +<div class="paragraph"><p><tt>key</tt> is a hashmap_entry structure (or user data structure that starts with +hashmap_entry) that has at least been initialized with the proper hash code +(via <tt>hashmap_entry_init</tt>).</p></div> +<div class="paragraph"><p>If an entry with matching hash code is found, <tt>key</tt> and <tt>keydata</tt> are passed +to <tt>hashmap_cmp_fn</tt> to decide whether the entry matches the key.</p></div> +</dd> +<dt class="hdlist1"> +<tt>void *hashmap_get_next(const struct hashmap *map, const void *entry)</tt> +</dt> +<dd> +<p> + Returns the next equal hashmap entry, or NULL if not found. This can be + used to iterate over duplicate entries (see <tt>hashmap_add</tt>). +</p> +<div class="paragraph"><p><tt>map</tt> is the hashmap structure.</p></div> +<div class="paragraph"><p><tt>entry</tt> is the hashmap_entry to start the search from, obtained via a previous +call to <tt>hashmap_get</tt> or <tt>hashmap_get_next</tt>.</p></div> +</dd> +<dt class="hdlist1"> +<tt>void hashmap_add(struct hashmap *map, void *entry)</tt> +</dt> +<dd> +<p> + Adds a hashmap entry. This allows to add duplicate entries (i.e. + separate values with the same key according to hashmap_cmp_fn). +</p> +<div class="paragraph"><p><tt>map</tt> is the hashmap structure.</p></div> +<div class="paragraph"><p><tt>entry</tt> is the entry to add.</p></div> +</dd> +<dt class="hdlist1"> +<tt>void *hashmap_put(struct hashmap *map, void *entry)</tt> +</dt> +<dd> +<p> + Adds or replaces a hashmap entry. If the hashmap contains duplicate + entries equal to the specified entry, only one of them will be replaced. +</p> +<div class="paragraph"><p><tt>map</tt> is the hashmap structure.</p></div> +<div class="paragraph"><p><tt>entry</tt> is the entry to add or replace.</p></div> +<div class="paragraph"><p>Returns the replaced entry, or NULL if not found (i.e. the entry was added).</p></div> +</dd> +<dt class="hdlist1"> +<tt>void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)</tt> +</dt> +<dd> +<p> + Removes a hashmap entry matching the specified key. If the hashmap + contains duplicate entries equal to the specified key, only one of + them will be removed. +</p> +<div class="paragraph"><p><tt>map</tt> is the hashmap structure.</p></div> +<div class="paragraph"><p><tt>key</tt> is a hashmap_entry structure (or user data structure that starts with +hashmap_entry) that has at least been initialized with the proper hash code +(via <tt>hashmap_entry_init</tt>).</p></div> +<div class="paragraph"><p>If an entry with matching hash code is found, <tt>key</tt> and <tt>keydata</tt> are +passed to <tt>hashmap_cmp_fn</tt> to decide whether the entry matches the key.</p></div> +<div class="paragraph"><p>Returns the removed entry, or NULL if not found.</p></div> +</dd> +<dt class="hdlist1"> +<tt>void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)</tt> +</dt> +<dt class="hdlist1"> +<tt>void *hashmap_iter_next(struct hashmap_iter *iter)</tt> +</dt> +<dt class="hdlist1"> +<tt>void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)</tt> +</dt> +<dd> +<p> + Used to iterate over all entries of a hashmap. +</p> +<div class="paragraph"><p><tt>hashmap_iter_init</tt> initializes a <tt>hashmap_iter</tt> structure.</p></div> +<div class="paragraph"><p><tt>hashmap_iter_next</tt> returns the next hashmap_entry, or NULL if there are no +more entries.</p></div> +<div class="paragraph"><p><tt>hashmap_iter_first</tt> is a combination of both (i.e. initializes the iterator +and returns the first entry, if any).</p></div> +</dd> +</dl></div> +</div> +</div> +<div class="sect1"> +<h2 id="_usage_example">Usage example</h2> +<div class="sectionbody"> +<div class="paragraph"><p>Here’s a simple usage example that maps long keys to double values.</p></div> +<div class="listingblock"> +<div class="content"></div></div> +</div> +</div> +<div class="sect1"> +<h2 id="_using_variable_sized_keys">Using variable-sized keys</h2> +<div class="sectionbody"> +<div class="paragraph"><p>The <tt>hashmap_entry_get</tt> and <tt>hashmap_entry_remove</tt> functions expect an ordinary +<tt>hashmap_entry</tt> structure as key to find the correct entry. If the key data is +variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable +to create a full-fledged entry structure on the heap and copy all the key data +into the structure.</p></div> +<div class="paragraph"><p>In this case, the <tt>keydata</tt> parameter can be used to pass +variable-sized key data directly to the comparison function, and the <tt>key</tt> +parameter can be a stripped-down, fixed size entry structure allocated on the +stack.</p></div> +<div class="paragraph"><p>See test-hashmap.c for an example using arbitrary-length strings as keys.</p></div> +</div> +</div> +</div> +<div id="footnotes"><hr /></div> +<div id="footer"> +<div id="footer-text"> +Last updated 2014-02-27 15:06:29 PST +</div> +</div> +</body> +</html> diff --git a/technical/api-hashmap.txt b/technical/api-hashmap.txt new file mode 100644 index 0000000..42ca234 --- /dev/null +++ b/technical/api-hashmap.txt
@@ -0,0 +1,235 @@ +hashmap API +=========== + +The hashmap API is a generic implementation of hash-based key-value mappings. + +Data Structures +--------------- + +`struct hashmap`:: + + The hash table structure. ++ +The `size` member keeps track of the total number of entries. The `cmpfn` +member is a function used to compare two entries for equality. The `table` and +`tablesize` members store the hash table and its size, respectively. + +`struct hashmap_entry`:: + + An opaque structure representing an entry in the hash table, which must + be used as first member of user data structures. Ideally it should be + followed by an int-sized member to prevent unused memory on 64-bit + systems due to alignment. ++ +The `hash` member is the entry's hash code and the `next` member points to the +next entry in case of collisions (i.e. if multiple entries map to the same +bucket). + +`struct hashmap_iter`:: + + An iterator structure, to be used with hashmap_iter_* functions. + +Types +----- + +`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`:: + + User-supplied function to test two hashmap entries for equality. Shall + return 0 if the entries are equal. ++ +This function is always called with non-NULL `entry` / `entry_or_key` +parameters that have the same hash code. When looking up an entry, the `key` +and `keydata` parameters to hashmap_get and hashmap_remove are always passed +as second and third argument, respectively. Otherwise, `keydata` is NULL. + +Functions +--------- + +`unsigned int strhash(const char *buf)`:: +`unsigned int strihash(const char *buf)`:: +`unsigned int memhash(const void *buf, size_t len)`:: +`unsigned int memihash(const void *buf, size_t len)`:: + + Ready-to-use hash functions for strings, using the FNV-1 algorithm (see + http://www.isthe.com/chongo/tech/comp/fnv). ++ +`strhash` and `strihash` take 0-terminated strings, while `memhash` and +`memihash` operate on arbitrary-length memory. ++ +`strihash` and `memihash` are case insensitive versions. + +`void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`:: + + Initializes a hashmap structure. ++ +`map` is the hashmap to initialize. ++ +The `equals_function` can be specified to compare two entries for equality. +If NULL, entries are considered equal if their hash codes are equal. ++ +If the total number of entries is known in advance, the `initial_size` +parameter may be used to preallocate a sufficiently large table and thus +prevent expensive resizing. If 0, the table is dynamically resized. + +`void hashmap_free(struct hashmap *map, int free_entries)`:: + + Frees a hashmap structure and allocated memory. ++ +`map` is the hashmap to free. ++ +If `free_entries` is true, each hashmap_entry in the map is freed as well +(using stdlib's free()). + +`void hashmap_entry_init(void *entry, unsigned int hash)`:: + + Initializes a hashmap_entry structure. ++ +`entry` points to the entry to initialize. ++ +`hash` is the hash code of the entry. + +`void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`:: + + Returns the hashmap entry for the specified key, or NULL if not found. ++ +`map` is the hashmap structure. ++ +`key` is a hashmap_entry structure (or user data structure that starts with +hashmap_entry) that has at least been initialized with the proper hash code +(via `hashmap_entry_init`). ++ +If an entry with matching hash code is found, `key` and `keydata` are passed +to `hashmap_cmp_fn` to decide whether the entry matches the key. + +`void *hashmap_get_next(const struct hashmap *map, const void *entry)`:: + + Returns the next equal hashmap entry, or NULL if not found. This can be + used to iterate over duplicate entries (see `hashmap_add`). ++ +`map` is the hashmap structure. ++ +`entry` is the hashmap_entry to start the search from, obtained via a previous +call to `hashmap_get` or `hashmap_get_next`. + +`void hashmap_add(struct hashmap *map, void *entry)`:: + + Adds a hashmap entry. This allows to add duplicate entries (i.e. + separate values with the same key according to hashmap_cmp_fn). ++ +`map` is the hashmap structure. ++ +`entry` is the entry to add. + +`void *hashmap_put(struct hashmap *map, void *entry)`:: + + Adds or replaces a hashmap entry. If the hashmap contains duplicate + entries equal to the specified entry, only one of them will be replaced. ++ +`map` is the hashmap structure. ++ +`entry` is the entry to add or replace. ++ +Returns the replaced entry, or NULL if not found (i.e. the entry was added). + +`void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`:: + + Removes a hashmap entry matching the specified key. If the hashmap + contains duplicate entries equal to the specified key, only one of + them will be removed. ++ +`map` is the hashmap structure. ++ +`key` is a hashmap_entry structure (or user data structure that starts with +hashmap_entry) that has at least been initialized with the proper hash code +(via `hashmap_entry_init`). ++ +If an entry with matching hash code is found, `key` and `keydata` are +passed to `hashmap_cmp_fn` to decide whether the entry matches the key. ++ +Returns the removed entry, or NULL if not found. + +`void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`:: +`void *hashmap_iter_next(struct hashmap_iter *iter)`:: +`void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`:: + + Used to iterate over all entries of a hashmap. ++ +`hashmap_iter_init` initializes a `hashmap_iter` structure. ++ +`hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no +more entries. ++ +`hashmap_iter_first` is a combination of both (i.e. initializes the iterator +and returns the first entry, if any). + +Usage example +------------- + +Here's a simple usage example that maps long keys to double values. +[source,c] +------------ +struct hashmap map; + +struct long2double { + struct hashmap_entry ent; /* must be the first member! */ + long key; + double value; +}; + +static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused) +{ + return !(e1->key == e2->key); +} + +void long2double_init(void) +{ + hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0); +} + +void long2double_free(void) +{ + hashmap_free(&map, 1); +} + +static struct long2double *find_entry(long key) +{ + struct long2double k; + hashmap_entry_init(&k, memhash(&key, sizeof(long))); + k.key = key; + return hashmap_get(&map, &k, NULL); +} + +double get_value(long key) +{ + struct long2double *e = find_entry(key); + return e ? e->value : 0; +} + +void set_value(long key, double value) +{ + struct long2double *e = find_entry(key); + if (!e) { + e = malloc(sizeof(struct long2double)); + hashmap_entry_init(e, memhash(&key, sizeof(long))); + e->key = key; + hashmap_add(&map, e); + } + e->value = value; +} +------------ + +Using variable-sized keys +------------------------- + +The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary +`hashmap_entry` structure as key to find the correct entry. If the key data is +variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable +to create a full-fledged entry structure on the heap and copy all the key data +into the structure. + +In this case, the `keydata` parameter can be used to pass +variable-sized key data directly to the comparison function, and the `key` +parameter can be a stripped-down, fixed size entry structure allocated on the +stack. + +See test-hashmap.c for an example using arbitrary-length strings as keys. diff --git a/technical/api-index.html b/technical/api-index.html index 1d7e784..ea8e7b8 100644 --- a/technical/api-index.html +++ b/technical/api-index.html
@@ -795,7 +795,7 @@ </li> <li> <p> -<a href="api-hash.html">hash API</a> +<a href="api-hashmap.html">hashmap API</a> </p> </li> <li> @@ -895,7 +895,7 @@ <div id="footnotes"><hr /></div> <div id="footer"> <div id="footer-text"> -Last updated 2014-02-24 13:03:32 PST +Last updated 2014-02-27 15:06:40 PST </div> </div> </body>
diff --git a/technical/api-index.txt b/technical/api-index.txt index 1a824f6..7d17550 100644 --- a/technical/api-index.txt +++ b/technical/api-index.txt
@@ -17,7 +17,7 @@ * link:api-directory-listing.html[directory listing API] * link:api-gitattributes.html[gitattributes API] * link:api-grep.html[grep API] -* link:api-hash.html[hash API] +* link:api-hashmap.html[hashmap API] * link:api-history-graph.html[history graph API] * link:api-in-core-index.html[in-core index API] * link:api-lockfile.html[lockfile API]
diff --git a/technical/bitmap-format.txt b/technical/bitmap-format.txt new file mode 100644 index 0000000..f8c18a0 --- /dev/null +++ b/technical/bitmap-format.txt
@@ -0,0 +1,164 @@ +GIT bitmap v1 format +==================== + + - A header appears at the beginning: + + 4-byte signature: {'B', 'I', 'T', 'M'} + + 2-byte version number (network byte order) + The current implementation only supports version 1 + of the bitmap index (the same one as JGit). + + 2-byte flags (network byte order) + + The following flags are supported: + + - BITMAP_OPT_FULL_DAG (0x1) REQUIRED + This flag must always be present. It implies that the bitmap + index has been generated for a packfile with full closure + (i.e. where every single object in the packfile can find + its parent links inside the same packfile). This is a + requirement for the bitmap index format, also present in JGit, + that greatly reduces the complexity of the implementation. + + - BITMAP_OPT_HASH_CACHE (0x4) + If present, the end of the bitmap file contains + `N` 32-bit name-hash values, one per object in the + pack. The format and meaning of the name-hash is + described below. + + 4-byte entry count (network byte order) + + The total count of entries (bitmapped commits) in this bitmap index. + + 20-byte checksum + + The SHA1 checksum of the pack this bitmap index belongs to. + + - 4 EWAH bitmaps that act as type indexes + + Type indexes are serialized after the hash cache in the shape + of four EWAH bitmaps stored consecutively (see Appendix A for + the serialization format of an EWAH bitmap). + + There is a bitmap for each Git object type, stored in the following + order: + + - Commits + - Trees + - Blobs + - Tags + + In each bitmap, the `n`th bit is set to true if the `n`th object + in the packfile is of that type. + + The obvious consequence is that the OR of all 4 bitmaps will result + in a full set (all bits set), and the AND of all 4 bitmaps will + result in an empty bitmap (no bits set). + + - N entries with compressed bitmaps, one for each indexed commit + + Where `N` is the total amount of entries in this bitmap index. + Each entry contains the following: + + - 4-byte object position (network byte order) + The position **in the index for the packfile** where the + bitmap for this commit is found. + + - 1-byte XOR-offset + The xor offset used to compress this bitmap. For an entry + in position `x`, a XOR offset of `y` means that the actual + bitmap representing this commit is composed by XORing the + bitmap for this entry with the bitmap in entry `x-y` (i.e. + the bitmap `y` entries before this one). + + Note that this compression can be recursive. In order to + XOR this entry with a previous one, the previous entry needs + to be decompressed first, and so on. + + The hard-limit for this offset is 160 (an entry can only be + xor'ed against one of the 160 entries preceding it). This + number is always positive, and hence entries are always xor'ed + with **previous** bitmaps, not bitmaps that will come afterwards + in the index. + + - 1-byte flags for this bitmap + At the moment the only available flag is `0x1`, which hints + that this bitmap can be re-used when rebuilding bitmap indexes + for the repository. + + - The compressed bitmap itself, see Appendix A. + +== Appendix A: Serialization format for an EWAH bitmap + +Ewah bitmaps are serialized in the same protocol as the JAVAEWAH +library, making them backwards compatible with the JGit +implementation: + + - 4-byte number of bits of the resulting UNCOMPRESSED bitmap + + - 4-byte number of words of the COMPRESSED bitmap, when stored + + - N x 8-byte words, as specified by the previous field + + This is the actual content of the compressed bitmap. + + - 4-byte position of the current RLW for the compressed + bitmap + +All words are stored in network byte order for their corresponding +sizes. + +The compressed bitmap is stored in a form of run-length encoding, as +follows. It consists of a concatenation of an arbitrary number of +chunks. Each chunk consists of one or more 64-bit words + + H L_1 L_2 L_3 .... L_M + +H is called RLW (run length word). It consists of (from lower to higher +order bits): + + - 1 bit: the repeated bit B + + - 32 bits: repetition count K (unsigned) + + - 31 bits: literal word count M (unsigned) + +The bitstream represented by the above chunk is then: + + - K repetitions of B + + - The bits stored in `L_1` through `L_M`. Within a word, bits at + lower order come earlier in the stream than those at higher + order. + +The next word after `L_M` (if any) must again be a RLW, for the next +chunk. For efficient appending to the bitstream, the EWAH stores a +pointer to the last RLW in the stream. + + +== Appendix B: Optional Bitmap Sections + +These sections may or may not be present in the `.bitmap` file; their +presence is indicated by the header flags section described above. + +Name-hash cache +--------------- + +If the BITMAP_OPT_HASH_CACHE flag is set, the end of the bitmap contains +a cache of 32-bit values, one per object in the pack. The value at +position `i` is the hash of the pathname at which the `i`th object +(counting in index order) in the pack can be found. This can be fed +into the delta heuristics to compare objects with similar pathnames. + +The hash algorithm used is: + + hash = 0; + while ((c = *name++)) + if (!isspace(c)) + hash = (hash >> 2) + (c << 24); + +Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag. +If implementations want to choose a different hashing scheme, they are +free to do so, but MUST allocate a new header flag (because comparing +hashes made under two different schemes would be pointless). diff --git a/technical/pack-protocol.html b/technical/pack-protocol.html index f2e44c0..cc6cea4 100644 --- a/technical/pack-protocol.html +++ b/technical/pack-protocol.html
@@ -1099,7 +1099,8 @@ during a prior round. This helps to ensure that at least one common ancestor is found before we give up entirely.</p></div> <div class="paragraph"><p>Once the <em>done</em> line is read from the client, the server will either -send a final <em>ACK obj-id</em> or it will send a <em>NAK</em>. The server only sends +send a final <em>ACK obj-id</em> or it will send a <em>NAK</em>. <em>obj-id</em> is the object +name of the last commit determined to be common. The server only sends ACK after <em>done</em> if there is at least one common base and multi_ack or multi_ack_detailed is enabled. The server always sends NAK after <em>done</em> if there is no common base found.</p></div> @@ -1306,7 +1307,7 @@ <div id="footnotes"><hr /></div> <div id="footer"> <div id="footer-text"> -Last updated 2014-01-17 14:43:28 PST +Last updated 2014-02-27 15:06:29 PST </div> </div> </body>
diff --git a/technical/pack-protocol.txt b/technical/pack-protocol.txt index c73b62f..39c6410 100644 --- a/technical/pack-protocol.txt +++ b/technical/pack-protocol.txt
@@ -338,7 +338,8 @@ ancestor is found before we give up entirely. Once the 'done' line is read from the client, the server will either -send a final 'ACK obj-id' or it will send a 'NAK'. The server only sends +send a final 'ACK obj-id' or it will send a 'NAK'. 'obj-id' is the object +name of the last commit determined to be common. The server only sends ACK after 'done' if there is at least one common base and multi_ack or multi_ack_detailed is enabled. The server always sends NAK after 'done' if there is no common base found.
diff --git a/technical/protocol-capabilities.html b/technical/protocol-capabilities.html index 75aaf3c..9de76ef 100644 --- a/technical/protocol-capabilities.html +++ b/technical/protocol-capabilities.html
@@ -802,6 +802,27 @@ </div> </div> <div class="sect1"> +<h2 id="_multi_ack_detailed">multi_ack_detailed</h2> +<div class="sectionbody"> +<div class="paragraph"><p>This is an extension of multi_ack that permits client to better +understand the server’s in-memory state. See pack-protocol.txt, +section "Packfile Negotiation" for more information.</p></div> +</div> +</div> +<div class="sect1"> +<h2 id="_no_done">no-done</h2> +<div class="sectionbody"> +<div class="paragraph"><p>This capability should only be used with the smart HTTP protocol. If +multi_ack_detailed and no-done are both present, then the sender is +free to immediately send a pack following its first "ACK obj-id ready" +message.</p></div> +<div class="paragraph"><p>Without no-done in the smart HTTP protocol, the server session would +end and the client has to make another trip to send "done" before +the server can send the pack. no-done removes the last round and +thus slightly reduces latency.</p></div> +</div> +</div> +<div class="sect1"> <h2 id="_thin_pack">thin-pack</h2> <div class="sectionbody"> <div class="paragraph"><p>A thin pack is one with deltas which reference base objects not @@ -968,7 +989,7 @@ <div id="footnotes"><hr /></div> <div id="footer"> <div id="footer-text"> -Last updated 2013-12-12 16:55:14 PST +Last updated 2014-02-27 15:06:29 PST </div> </div> </body>
diff --git a/technical/protocol-capabilities.txt b/technical/protocol-capabilities.txt index e3e7924..e174343 100644 --- a/technical/protocol-capabilities.txt +++ b/technical/protocol-capabilities.txt
@@ -69,6 +69,24 @@ Without multi_ack the client would have sent that c-b-a chain anyway, interleaved with S-R-Q. +multi_ack_detailed +------------------ +This is an extension of multi_ack that permits client to better +understand the server's in-memory state. See pack-protocol.txt, +section "Packfile Negotiation" for more information. + +no-done +------- +This capability should only be used with the smart HTTP protocol. If +multi_ack_detailed and no-done are both present, then the sender is +free to immediately send a pack following its first "ACK obj-id ready" +message. + +Without no-done in the smart HTTP protocol, the server session would +end and the client has to make another trip to send "done" before +the server can send the pack. no-done removes the last round and +thus slightly reduces latency. + thin-pack ---------
